/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhong
 *
 */
public class KeysandRooms {
	public boolean canVisitAllRooms(List<List<Integer>> rooms) {
		int n = rooms.size();
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(0);
		boolean[] visited = new boolean[n];
		visited[0] = true;
		int cnt = 1;// 拿到的钥匙对应的房间个数
		while (!queue.isEmpty()) {
			// 从房间拿出钥匙
			Integer room = queue.poll();
			for (Integer key : rooms.get(room)) {// 该房间里的钥匙
				if (!visited[key]) {// 拿到的不同的钥匙记录
					queue.offer(key);
					visited[key] = true;
					cnt++;
					if (cnt == n) {
						return true;
					}
				}
			}
		}
		return cnt == n;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] s = { { 1, 3 }, { 3, 0, 1 }, { 2 }, { 0 } };
		List<List<Integer>> rooms = new ArrayList<>();
		for (int i = 0; i < s.length; i++) {
			ArrayList<Integer> list = new ArrayList<>();
			for (int j = 0; j < s[i].length; j++) {
				list.add(s[i][j]);
			}
			rooms.add(list);
		}
		System.out.println(new KeysandRooms().canVisitAllRooms(rooms));
	}

}
